BOJ23022 숙제

풀이

숙제를 처리하고 휴식할 필요가 없다면 그냥 숙제가 공개되자마자 다 처리하면 됩니다. 하지만 반드시 1의 휴식시간을 가져야 하기 때문에, 특정 시점에서 공개되어 있는 여러개의 숙제 중에서 하나만 처리할 수 있습니다. 그 하나는 공개되어있는 숙제들 중에서 제일 벌점계수가 큰 것을 고르면 되는것을 직관적으로 알 수 있고 증명도 exchange argument로 쉽게 가능합니다. 따라서 숙제를 (시간,-벌점)으로 정렬한 순서대로 스위핑하면서 특정시점에 공개되어있는 숙제들을 PQ로 잘 관리해주면 문제를 풀 수 있습니다. 코드: http://boj.kr/68a1a528934240f794ace00860f836cb